package com.datastructure;

import java.util.Arrays;

public class ThreeSumCloser {
    public static void main(String[] args) {
        System.out.println(threeSumClosest(new int[]{-1, 2, 1,-4}, 1));
        double result = 1;
        for(int i=1;i<=170;i++){
            result = result * i ;
        }

        System.out.println("result:" + result);
    }

    public static int threeSumClosest(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int sum = 0;
        if (nums.length <= 3) {
            for (int i : nums) {
                sum += i;
            }
            return sum;
        }

        Arrays.sort(nums);
        sum = nums[0]+nums[1]+nums[2] ;
        for (int i = 0; i <= nums.length - 3; i++) { //固定一个
            int fixValue = nums[i];

            int j = i + 1, k = nums.length - 1;
            while (j < k ) {
                int curSum = fixValue + nums[j] + nums[k];
                if (curSum == target) {
                    return curSum;
                } else if (curSum > target) {
                    if (Math.abs(sum - target) > Math.abs(curSum - target)) {
                        sum = curSum;
                    }
                    k--;
                } else { //sum<target
                    if (Math.abs(sum - target) > Math.abs(curSum - target)) {
                        sum = curSum;
                    }
                    j++;
                }
            }
        }
        return sum;
    }
}
